package 算法.leetcode.stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/2/17
 */
public class WenCha {

    public static void main(String[] args) {
        int[] array = dailyTemperature(new int[]{73, 74, 75, 71, 69, 72, 76, 73});
        System.out.println(Arrays.toString(array));
    }

    public static int[] dailyTemperature(int[] T) {
        int[] ans = new int[T.length];
        Stack<Integer> s = new Stack<Integer>(); // 这⾥放元素索引，⽽不是元素
        //
        for (int i = T.length - 1; i >= 0; i--) {
            while (!s.empty() && T[s.peek()] <= T[i]) {
                // 栈内的数据是递增的
                // 配合后面的s.push(i);把当前循环的数据放到单调栈中合适的位置
                s.pop();
            }
            // 栈顶的数据是大于当前数据的 计算两者索引的差值即可
            ans[i] = s.empty() ? 0 : (s.peek() - i);
            // 得到索引间距
            s.push(i);
            // 加⼊索引，⽽不是元素
        }
        return ans;
    }
}
